#include "Graph.hpp"
#include <string>
#include <cstring>

void BDFS_test()
{
    string a[] = { "张三", "李四", "王五", "赵六", "周七" };
    matrix::Graph<string, int> g1(a, sizeof(a)/sizeof(string));
    g1.AddEdge("张三", "李四", 1);
    g1.AddEdge("张三", "王五", 2);
    g1.AddEdge("王五", "赵六", 3);
    g1.AddEdge("王五", "周七", 4);
    g1.BFS("张三");
    cout << endl;
    g1.DFS("张三");
}

void Mintree_test()
{
    const char* str = "abcdefghi";
    matrix::Graph<char, int> g(str, strlen(str));
    g.AddEdge('a', 'b', 4);
    g.AddEdge('a', 'h', 8);
    //g.AddEdge('a', 'h', 9);
    g.AddEdge('b', 'c', 8);
    g.AddEdge('b', 'h', 11);
    g.AddEdge('c', 'i', 2);
    g.AddEdge('c', 'f', 4);
    g.AddEdge('c', 'd', 7);
    g.AddEdge('d', 'f', 14);
    g.AddEdge('d', 'e', 9);
    g.AddEdge('e', 'f', 10);
    g.AddEdge('f', 'g', 2);
    g.AddEdge('g', 'h', 1);
    g.AddEdge('g', 'i', 6);
    g.AddEdge('h', 'i', 7);

    matrix::Graph<char, int> KminTree;
    cout << "Kruskal:" << g.Kruskal(KminTree) << endl;
    KminTree.Print();
    cout << "=============================" << endl;

    matrix::Graph<char, int> PminTree;
    cout << "Prim:" << g.Prim(PminTree, 'a') << endl;
    PminTree.Print();
}

int main()
{
    Mintree_test();
    return 0;
}